package impl;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Keevu
 * Date: 05/10/11
 * Time: 14:17
 * To change this template use File | Settings | File Templates.
 */
public class QuickSorterThreeWayPartition extends AbstractSorter {

    public QuickSorterThreeWayPartition() {
        super(SorterType.QUICK_THREE_PARTITION);
    }


    public <T> void sort(Comparator<T> tComparator, List<T> ts) {
        sort(tComparator, ts, 0, ts.size()-1);
    }

    public <T> void sort(Comparator tComparator, List ts, int l, int r) {
        if (l >= r) {
            return;
        }
        int i = l;
        int j = r;
        int p = l;
        int q = r;


        int pivot = ((l + r) / 2);

        while (i < j) {
            while (greater(tComparator, ts, pivot, i)) {
                i++;
            }
            while (greater(tComparator, ts, j, pivot)) {
                j--;
            }
            if (j == l) {
                break;
            }
            if (i >= j) {
                break;
            }

            if (i < j) {
                swap(ts, i, j);
            }
            if (equals(tComparator, ts, i, pivot)) {
                p++;
                swap(ts, p, i);
            }
            if (equals(tComparator, ts, j, pivot)) {
                q--;
                swap(ts, q, j);
            }
        }
        swap(ts, l, r);


        for (int k = l; k < p; k++, i--) {
            swap(ts,k,i);
        }
        for (int k = r; k > q; k--, j++) {
            swap(ts,j,k);
        }

    }
}
